package Datastruct.Kruskal;

import java.util.Scanner;

//分治算法  --汉诺塔问题
public class HanoiTower {
    public static int k = 1;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入盘子是个数：");
        int i = scanner.nextInt();
        System.out.println(i + "个盘子的移动次序为：");


        hanoi(i, 'A', 'B', 'C');
        System.out.println(i + "个盘子一共要移动" + (k - 1) + "次");

    }

    public static void hanoi(int num, char a, char b, char c) {
        if (num == 1) {
            System.out.println("第" + k + "次移动：由" + a + "移动到" + c);
            k++;
        } else {
            hanoi(num - 1, a, c, b);

            hanoi(1, a, b, c);
            hanoi(num - 1, b, a, c);
        }

    }
}
